#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>

using namespace std;

typedef struct AVLTNode
{
    int data;
    int height;
    AVLTNode *left, *right;
}AVLTNode, *AVLTree;

AVLTree NewNode(AVLTree &T,int e){
    T->data = e;
    T->height = 1;
    T->left = NULL;
    T->right = NULL;
    return T;
}

// getHeight 获取树的高度
int getHeight(AVLTNode *node) {
    if(node)
        return node->height;
    return 0;
}

// getBalanceFactor 求平衡因子
int getBalanceFactor(AVLTNode *node){
    if(node)
        return getHeight(node->left) - getHeight(node->right);
    return 0;
}

// inOrder 中序遍历
void inOrder(AVLTree T, vector<int> keys) {
    if(!T)
        return;
    inOrder(T,keys);
    keys.push_back(T->data);
    inOrder(T,keys);
}

// isBST 是否符合二叉搜索树
bool isBST(AVLTree T) {
    vector<int> keys;
    inOrder(T, keys);
    for(int i = 1; i < keys.size(); i++) {
        if(keys[i-1] > keys[i])
            return false;
    }
    return true;
}

// isBalanced 是否平衡
bool isBalanced(AVLTree T) {
    if(!T)
        return true;
    int balanceFactor = getBalanceFactor(T);
    if(abs(balanceFactor) > 1) 
        return false;
    return isBalanced(T->left) && isBalanced(T->right);
}

// rightRotate 右旋转
AVLTree rightRotate(AVLTree &y) {
    AVLTNode *x = y->left;
    AVLTNode *tmp = y->right;
    
    x->right = y;
    y->left = tmp;

    y->height = max(getHeight(y->left), getHeight(y->right));
    x->height = max(getHeight(x->left), getHeight(x->right));
    return x;
}

// leftRotate 右旋转
AVLTree leftRotate(AVLTree &y) {
    AVLTNode *x = y->right;
    AVLTNode *tmp = y->left;
    
    x->left = y;
    y->right = tmp;

    y->height = max(getHeight(y->left), getHeight(y->right));
    x->height = max(getHeight(x->left), getHeight(x->right));
    return x;
}

// add 添加元素
AVLTree add(AVLTree &T, int e) {
    if (!T)
        return NewNode(T,e);
        
    if(T->data < e)
        T->left = add(T->left,e);
    else if(T->data > e)
        T->right = add(T->right,e);
    else
        T->data = e;

    // 更新高度
    T->height = 1 + max(T->left->height, T->right->height);
    
    // 求平衡因子
    int balanceFactor = getBalanceFactor(T);
    
    // LL
    if(balanceFactor > 1 && getBalanceFactor(T->left) >= 0)
        return rightRotate(T);              // 右旋
    
    // RR
    if(balanceFactor  < -1 && getBalanceFactor(T->right) <= 0)
        return leftRotate(T);               // 左旋
    
    // LR
    if(balanceFactor > 1 && getBalanceFactor(T->left) < 0) {
        T->left = leftRotate(T->left);      // 左旋
        return rightRotate(T);              // 右旋
    }

    // RL
    if(balanceFactor > -1 && getBalanceFactor(T->right) > 0) {
        T->left = rightRotate(T->right);    // 左旋
        return leftRotate(T);               // 右旋
    }

    return T;
}

int main() {
    
}